﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using Xunit;
namespace LeetCode.CodeDay
{
    public partial class Code
    {
        /// <summary>
        /// 给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
        /// 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
        /// 返回被除数 dividend 除以除数 divisor 得到的 商 。
        /// 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是[−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231。
        /// </summary>
        /// <param name="dividend"></param>
        /// <param name="divisor"></param>
        /// <returns></returns>
        public int Divide(int dividend, int divisor)
        {
            if (divisor == int.MinValue && divisor == -1)
                return int.MaxValue;
            if (dividend == 0)
                return 0;
            if (dividend == int.MinValue)
            {
                if (divisor == -1)
                    return int.MaxValue;
                if (divisor == 1)
                    return dividend;
            }
            if (divisor == int.MinValue)
            {
                return dividend == int.MinValue ? 1 : 0;
            }
            bool isFS = divisor > 0 && dividend < 0 || divisor < 0 && dividend > 0;
            if (isFS)
            {
                if (dividend > 0)
                    dividend = -dividend;
                else if (divisor > 0)
                    divisor = -divisor;
            }
            else if (divisor > 0)
            {
                divisor = -divisor;
                dividend = -dividend;
            }
            if (dividend > divisor)
                return 0;

            Func<int, int, int> chuMax = (a, b) =>
            {
                int movi = 0;

                while (a <= b)
                {
                    movi++;
                    if (b << 1 > b)
                        break;
                    b <<= 1;
                }
                return movi - 1;
            };
            int z = dividend;
            int rs = 0;
            while (z <= divisor)
            {
                int thisJ = chuMax(z, divisor);
                rs += 1 << thisJ;
                z = z - (divisor << (thisJ));
            }
            return isFS ? -rs : rs;
        }
        /// <summary>
        /// 串联所有单词的子串
        /// 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。     
        /// s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
        /// 例如，如果 words = ["ab", "cd", "ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
        /// "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
        /// 返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案
        /// </summary>
        /// <param name="s"></param>
        /// <param name="words"></param>
        /// <returns></returns>
        public IList<int> FindSubstring(string s, string[] words)
        {
            Func<List<string>, string?, List<string>> getSplitList = (a, b) =>
            {
                Dictionary<string, int> lrs = new Dictionary<string, int>();
                if (b == null)
                    return a;
                int p = b.Length;
                for (int k = 0; k < a.Count; k++)
                {
                    for (int i = 0; i <= a[k].Length; i += p)
                    {
                        string a1 = a[k].Insert(i, b);
                        if (lrs.ContainsKey(a1) == false)
                        {
                            if (s.IndexOf(a1) > -1)
                                lrs.Add(a1, 0);
                        }
                    }
                }
                return lrs.Keys.ToList();
            };
            var initList = new List<string>() { words[0] };
            for (int n = 1; n < words.Length; n++)
            {
                initList = getSplitList(initList, words[n]).Distinct().ToList();
            }
            var strLength = words[0].Length * words.Length;
            var strList = initList.ToList();
            List<int> rs = new List<int>();

            for (int i = 0; i < strList.Count; i++)
            {
                string sbak = s;
                var index = sbak.LastIndexOf(strList[i]);
                while (index > -1)
                {
                    rs.Add(index);
                    if (index == 0)
                        break;
                    sbak = sbak.Substring(0, index + strLength - 1);
                    index = sbak.LastIndexOf(strList[i]);
                }

            }
            return rs;
        }
    }
}